package sword.chapter6Stack;

import java.util.Stack;

/**
 * 每日温度
 * 如果输入数组[35, 31, 33, 36, 34]，那么输出为[3, 1, 1, 0, 0]。
 *
 * 栈中元素存值   输入值的下标
 * 辅助的数据结构  返回结果result数组
 * 什么时候入栈   1栈空 2栈顶大于等于当前值
 * 什么时候出栈   循环 1栈不为空 2栈顶小于当前值 同时计算更新辅助数据结构
 *
 * @author K
 * @date 2021/12/4 14:21
 */
public class S38DailyTemperatures {
    public static int[] s38(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) {
                result[stack.peek()] = i-stack.peek();
                stack.pop();

                // 等价
//                int prev = stack.pop();
//                result[prev] = i - prev;
            }

//            if (stack.empty() || temperatures[stack.peek()] >= temperatures[i]) {
                stack.push(i);
//            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] ints = {35, 31, 33, 36, 34};
        int[] result = s38(ints);
        System.out.println();
    }
}
